function ListNode(key, data) {
  this.key = key
  this.data = data
  this.prev = null
  this.next = null
}

function LinkedList() {
  // 使用两个空节点，使得真正的头尾节点跟其它节点操作一致
  this.front = new ListNode()
  this.tail = new ListNode()
  this.front.next = this.tail
  this.tail.prev = this.front
  // 使用hash加速
  this.map = {}
}
LinkedList.prototype.addFirst = function (key, node) {
  const prevNode = this.front
  const nextNode = this.front.next
  // node的前驱指向front
  node.prev = prevNode
  // node的后继指向front.next
  node.next = nextNode
  // front.next指向node
  prevNode.next = node
  // front.next.prev指向node
  nextNode.prev = node

  // 查询加速
  this.map[key] = node
}
LinkedList.prototype.remove = function (node) {
  const prevNode = node.prev
  const nextNode = node.next
  // 删除节点
  // -- 节点前驱后继指向节点后继
  prevNode.next = nextNode
  // -- 节点后继的前驱指向节点前驱
  nextNode.prev = prevNode

  // 删除map
  delete this.map[node.key]
}
LinkedList.prototype.removeLast = function () {
  const last = this.tail.prev
  this.remove(last)
}
LinkedList.prototype.get = function (key) {
  // 存现节点
  const node = this.map[key]
  if (node === undefined) 
      return null
  return node
}



/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
  this._capacity = capacity
  this._count = 0
  this._linked = new LinkedList()
};

/** 
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
  const node = this._linked.get(key)
  // 节点不存在
  if (node === null) 
      return -1
  // 节点存在
  // -- 删除节点
  this._linked.remove(node)
  // -- 添加节点
  this._linked.addFirst(key, node)
  return node.data
};

/** 
* @param {number} key 
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
  const node = this._linked.get(key)
  // 节点存在
  if (node) {
      // -- 删除节点
      this._linked.remove(node)
      // -- 更新节点data
      node.data = value
      // -- 添加节点
      this._linked.addFirst(key, node)
      return
  }
  // 节点不存在
  // -- capacity越界
  if (this._count === this._capacity) {
      this._linked.removeLast()
      this._count--
  }
  // -- capacity在范围内
  // ---- 添加到首节点
  const nn = new ListNode(key, value)
  this._linked.addFirst(key, nn)
  this._count++
};

const lru = new LRUCache(2);
console.log(lru.put(1, 1)); // 缓存是 {1=1}
console.log(lru.put(2, 2)); // 缓存是 {1=1, 2=2}
console.log(lru.get(1));    // 返回 1
console.log(lru.put(3, 3)); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
console.log(lru.get(2));    // 返回 -1 (未找到)
console.log(lru.put(4, 4)); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
console.log(lru.get(1));    // 返回 -1 (未找到)
console.log(lru.get(3));    // 返回 3
console.log(lru.get(4));    // 返回 4